package secondary

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
/*
	给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
	叶子节点 是指没有子节点的节点。

	示例 1：
	输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
	输出：[[5,4,11,2],[5,8,4,5]]

	示例 2：
	输入：root = [1,2,3], targetSum = 5
	输出：[]
	示例 3：

	输入：root = [1,2], targetSum = 0
	输出：[]

	提示：

	树中节点总数在范围 [0, 5000] 内
	-1000 <= Node.val <= 1000
	-1000 <= targetSum <= 1000
	注意：本题与主站 113题相同：https://leetcode-cn.com/problems/path-sum-ii/

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func pathSum(root *TreeNode, target int) [][]int {
	result := make([][]int, 0)
	res := make([]int, 0)
	preOrder(root, target, 0, res, &result)
	return result
}

func preOrder(root *TreeNode, target int, curSum int, res []int, result *[][]int) {
	if nil == root {
		return
	}

	if root.Val+curSum == target {
		if root.Left == nil && root.Right == nil {
			*result = append(*result, append(append([]int{}, res...), root.Val))
			return
		}
	}
	preOrder(root.Left, target, curSum+root.Val, append(res, root.Val), result)
	preOrder(root.Right, target, curSum+root.Val, append(res, root.Val), result)
}

